import utils.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/4 12:37
 * @description:
 */
public class Solution103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count =0;
        while (!queue.isEmpty()){
            int size = queue.size();
            LinkedList<Integer> temp = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode p =queue.poll();
                if(count%2==0){
                    temp.addLast(p.val);
                }else{
                    temp.addFirst(p.val);
                }
                if(p.left!=null) queue.add(p.left);
                if(p.right!=null) queue.add(p.right);

            }
            count++;
            res.add(temp);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution103 solution = new Solution103();
        TreeNode root = TreeNode.buildTree(new int[]{3, 9, 20, -1, -1, 15, 7});
        List<List<Integer>> res = solution.zigzagLevelOrder(root);
        System.out.println(res);
    }
}
